package com.maishi.programmer.jainzhioffer;

/**
 * Created by brossdong on 2018/4/3.
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 */
public class TestProblem33 {

    /*public static boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) return false;
        //得出树的根节点
        int treeRoot = sequence[sequence.length - 1];
        for (int i = 0;i < sequence.length - 1;i++) {
            //找出左子树所有节点
            if (sequence[i] < treeRoot) {
                break;
            }
            for (int j = i;j < sequence.length - 1;j++) {
                if (sequence[j] > treeRoot)
                    return true;
            }
        }
        boolean b = VerifySquenceOfBST(sequence);

        return b;
    }*/

    public static boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) return false;
        boolean res =getRes(sequence,0,sequence.length-1);
        return res;
    }

    public static boolean getRes (int[] s,int start,int end) {
        int i = 0;
        int j = 0;

        //
        if (end - start <= 0) return true;

        //找出左子树中最后一个树
        for (i = start;i < end;i++)
            if (s[i] > s[end])
                break;

        //判断右子树
        for (j = i;j < end;j++)
            if (s[j] < s[end])
                return false;

        boolean left=true;
        boolean right=true;
        if (i > 0)
            left = getRes(s,start,i - 1);
        if (i < s.length - 1)
            right = getRes(s,i,end-1);

        return left&&right;
    }



    public static void main(String[] args) {
        int[] sequence = {5,7,6,9,11,10,8};
        System.out.println(VerifySquenceOfBST(sequence));
    }
}
